#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e5 + 5;

int n, m;
int a[N];
struct Node {
  char op;
  int a, b, k;
} b[N];
int c[N << 1], num;
struct SNode {
  int sum;
  int ch[2];
} tr[N * 40];
#define sum(p) tr[p].sum
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]

int newnode() {
  static int tot = 0;
  return ++tot;
}
int root[N << 1];
void update(int x, int d, int& p, int l, int r) {
  if (!p) p = newnode();
  sum(p) += d;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(x, d, lc(p), l, mid);
  else
    update(x, d, rc(p), mid + 1, r);
}
int query(int L, int R, int p, int l, int r) {
  if (L <= l && R >= r) return sum(p);
  int mid = (l + r) >> 1;
  int res = 0;
  if (L <= mid) res += query(L, R, lc(p), l, mid);
  if (R > mid) res += query(L, R, rc(p), mid + 1, r);
  return res;
}
void build() { rep(i, 1, n) update(i, 1, root[a[i]], 1, n); }
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, m) {
    cin >> b[i].op;
    if (b[i].op == 'C')
      cin >> b[i].a >> b[i].k;
    else
      cin >> b[i].a >> b[i].b >> b[i].k;
  }
  rep(i, 1, n) c[i] = a[i];
  rep(i, 1, m) c[n + i] = b[i].k;
  sort(c + 1, c + n + m + 1);
  num = unique(c + 1, c + n + m + 1) - c - 1;
  rep(i, 1, n) a[i] = lower_bound(c + 1, c + num + 1, a[i]) - c;
  rep(i, 1, m) b[i].k = lower_bound(c + 1, c + num + 1, b[i].k) - c;
  build();
  rep(i, 1, m) {
    if (b[i].op == 'C') {
      int x = b[i].a;
      int id = a[x];
      update(x, -1, root[id], 1, n);
      a[x] = b[i].k;
      id = a[x];
      update(x, 1, root[id], 1, n);
    } else {
      int l = b[i].a, r = b[i].b, id = b[i].k;
      cout << query(l, r, root[id], 1, n) << endl;
    }
  }
  return 0;
}